#ifndef _BLT_HPP_
#define _BLT_HPP_

#include<iostream>
#include<vector>
#include<cstdlib>
using namespace std;

template<typename T>
void random_shuffle(vector<T> &target){
    int len=target.size();
    for(int i=len-1;i>0;i--){
        int j=rand()%i;
        swap(target[i],target[j]);
    }
}

template <typename T>
class avl_tree{
    private:

    struct node{
        T element;
        int num;
        int height;
        node *left;
        node *right;
    };

    inline void create_node(node* &theNode, const T & theElement, node *ls, node *rs){
        theNode=new node;
        theNode->element=theElement;
        theNode->left=ls; theNode->right=rs;
        theNode->num=1; theNode->height=1;
    }

    node *root;
    bool isempty;

    const int get_height(node* theNode){
        if(theNode==nullptr) return 0;
        else return theNode->height;
    }
    void left_rotation(node* &theNode){
        node* ls=theNode->left;
        theNode->left=ls->right;
        ls->right=theNode;
        theNode->height=max(get_height(theNode->left),get_height(theNode->right))+1;
        ls->height=max(get_height(ls->left),get_height(ls->right))+1;
        theNode=ls;
    }
    void right_rotation(node* &theNode){
        node* rs=theNode->right;
        theNode->right=rs->left;
        rs->left=theNode;
        theNode->height=theNode->height=max(get_height(theNode->left),get_height(theNode->right))+1;
        rs->height=max(get_height(rs->left),get_height(rs->right))+1;
        theNode=rs;
    }
    void balance(node* &theNode){
        if(theNode==nullptr) return;
        
        if(get_height(theNode->left)-get_height(theNode->right)>1){
            if(get_height(theNode->left->left)>=get_height(theNode->left->right)){
                left_rotation(theNode);
            }else{
                right_rotation(theNode->left);
                left_rotation(theNode);
            }
        }else if(get_height(theNode->right)-get_height(theNode->left)>1){
            if(get_height(theNode->right->right)>=get_height(theNode->right->left)){
                right_rotation(theNode);
            }else{
                left_rotation(theNode->right);
                right_rotation(theNode);
            }
        }
        theNode->height=max(get_height(theNode->left),get_height(theNode->right))+1;
    }
    void insert(const T & object, node *&theNode){
        if(theNode==nullptr) create_node(theNode,object,nullptr,nullptr);
        else if(object>theNode->element) insert(object,theNode->right);
        else if(object<theNode->element) insert(object,theNode->left);
        else theNode->num++;
        balance(theNode);
    }
    void erase(node *theNode){
        if(theNode->left==nullptr||theNode->right==nullptr){
            delete theNode;
            return;
        }
        if(theNode->left!=nullptr) erase(theNode->left);
        if(theNode->right!=nullptr) erase(theNode->right); 
    }
    const T& find_min(node* theNode){
        if(theNode->left==nullptr) return theNode->element;
        else find_min(theNode->left);
    }
    const T& find_max(node* theNode){
        if(theNode->right==nullptr) return theNode->element;
        else find_max(theNode->right);
    }
    void mid_print(node *theNode){
        if(theNode->left!=nullptr) mid_print(theNode->left);
        cout<<theNode->element<<' ';
        if(theNode->right!=nullptr) mid_print(theNode->right);
        return;
    }
    void mid_out(node *theNode,vector<T>& target){
        if(theNode->left!=nullptr) mid_out(theNode->left,target);
        for(int i=1;i<=theNode->num;i++) target.push_back(theNode->element);
        if(theNode->right!=nullptr) mid_out(theNode->right,target);
        return;
    }

    public:
    avl_tree(){
        root=nullptr;
    }
    ~avl_tree(){
        if(root==nullptr) return;
        erase(root);
    }
    bool tree_empty() const{
        return isempty;
    }
    void avl_insert(const T& object){
        insert(object,root);
    }
    const T& min_ele(){
        if(tree_empty()){
            cout<<"Error! AVL Tree is empty!"<<endl;
            return root->element;
        }
        return find_min(root);
    }
    const T& max_ele(){
        if(tree_empty()){
            cout<<"Error! AVL Tree is empty!"<<endl;
            return root->element;
        }
        return find_max(root);
    }
    void avl_midprint(){
        mid_print(root);
    }
    void avl_midout(vector<T>& _target){
        mid_out(root,_target);
    }  
};

template <typename T>
void AVL_sort(vector<T>& _data){
        avl_tree<T> tree;
        for(int i=0;i<_data.size();i++) tree.avl_insert(_data[i]);
        int size=_data.size();
        for(int i=0;i<size;i++) _data.pop_back();
        tree.avl_midout(_data);
}

template <typename T>
class sp_tree{
    private:

    struct node{
        T element;
        int num;
        int height;
        node *left;
        node *right;

        node *fa;
    };

    inline void create_node(node* &theNode, const T & theElement, node *ls, node *rs, node *pa){
        theNode=new node;
        theNode->element=theElement;
        theNode->left=ls; theNode->right=rs; theNode->fa=pa;
        theNode->num=1; theNode->height=1;
    }

    node *root;
    bool isempty;

    const int get_height(node* theNode){
        if(theNode==nullptr) return 0;
        else return theNode->height;
    }
    void left_rotation(node* &theNode){
        node* ls=theNode->left;
        theNode->left=ls->right;
        if(theNode->left!=nullptr) theNode->left->fa=theNode;
        ls->right=theNode;
        ls->fa=theNode->fa;
        theNode->fa=ls;
        theNode=ls;
    }
    void right_rotation(node* &theNode){
        node* rs=theNode->right;
        theNode->right=rs->left;
        if(theNode->right!=nullptr) theNode->right->fa=theNode;
        rs->left=theNode;
        rs->fa=theNode->fa;
        theNode->fa=rs;
        theNode=rs;
    }
    const T get_ele(node* theNode){
        if(theNode==nullptr) return 0;
        else return theNode->element;
    }
    node* find(const T & num){
        node* index=root;
        if(index==nullptr) return nullptr;
        while(index->element!=num){
            if(index->element>num) index=index->left;
            else index=index->right;
        }
        return index;
    }
    void splay(node* &theNode){
        if(theNode==nullptr) return;
        else if(theNode->fa==nullptr) return;
        else if(theNode->fa->fa==nullptr){
            if(theNode==root->left) left_rotation(root);
            else right_rotation(root);
        }else{
            if(theNode==theNode->fa->left&&theNode->fa==theNode->fa->fa->left){
                if(theNode->fa->fa->fa==nullptr){
                    left_rotation(root);
                    left_rotation(root);
                }
                else{
                    if(theNode->fa->fa==theNode->fa->fa->fa->left) left_rotation(theNode->fa->fa->fa->left);
                    else left_rotation(theNode->fa->fa->fa->right);
                    if(theNode->fa==theNode->fa->fa->left) left_rotation(theNode->fa->fa->left);
                    else left_rotation(theNode->fa->fa->right);
                }
            }else if(theNode==theNode->fa->right&&theNode->fa==theNode->fa->fa->right){
                if(theNode->fa->fa->fa==nullptr){
                    right_rotation(root);
                    right_rotation(root);
                }
                else{
                    if(theNode->fa->fa==theNode->fa->fa->fa->left) right_rotation(theNode->fa->fa->fa->left);
                    else right_rotation(theNode->fa->fa->fa->right);
                    if(theNode->fa==theNode->fa->fa->left) right_rotation(theNode->fa->fa->left);
                    else right_rotation(theNode->fa->fa->right);
                }
            }else if(theNode==theNode->fa->left&&theNode->fa==theNode->fa->fa->right){
                left_rotation(theNode->fa->fa->right);
                if(theNode->fa->fa==nullptr) right_rotation(root);
                else if(theNode->fa==theNode->fa->fa->left) right_rotation(theNode->fa->fa->left);
                else right_rotation(theNode->fa->fa->right);
            }else if(theNode==theNode->fa->right&&theNode->fa==theNode->fa->fa->left){
                right_rotation(theNode->fa->fa->left);
                if(theNode->fa->fa==nullptr) left_rotation(root);
                else if(theNode->fa==theNode->fa->fa->left) left_rotation(theNode->fa->fa->left);
                else left_rotation(theNode->fa->fa->right);
            }
        }
    }
    void insert(const T & object, node *&theNode,node* pa){
        if(theNode==nullptr) create_node(theNode,object,nullptr,nullptr,pa);
        else if(object>theNode->element){
            insert(object,theNode->right,theNode);
        }
        else if(object<theNode->element){
            insert(object,theNode->left,theNode);   
        }
        else theNode->num++;
    }
    void erase(node *theNode){
        if(theNode->left==nullptr||theNode->right==nullptr){
            delete theNode;
            return;
        }
        if(theNode->left!=nullptr) erase(theNode->left);
        if(theNode->right!=nullptr) erase(theNode->right); 
    }
    const T& find_min(node* theNode){
        if(theNode->left==nullptr) return theNode->element;
        else find_min(theNode->left);
    }
    const T& find_max(node* theNode){
        if(theNode->right==nullptr) return theNode->element;
        else find_max(theNode->right);
    }
    void mid_print(node *theNode){
        if(theNode->left!=nullptr) mid_print(theNode->left);
        cout<<theNode->element<<' '<<get_ele(theNode->fa)<<' '<<get_ele(theNode->left)<<' '<<get_ele(theNode->right)<<endl;
        if(theNode->right!=nullptr) mid_print(theNode->right);
        return;
    }
    void mid_out(node *theNode,vector<T>& target){
        if(theNode->left!=nullptr) mid_out(theNode->left,target);
        for(int i=1;i<=theNode->num;i++) target.push_back(theNode->element);
        if(theNode->right!=nullptr) mid_out(theNode->right,target);
        return;
    }

    public:
    sp_tree(){
        root=nullptr;
    }
    ~sp_tree(){
        if(root==nullptr) return;
        erase(root);
    }
    bool tree_empty() const{
        return isempty;
    }
    void sp_insert(const T& object){
        insert(object,root,nullptr);
        node* temp=find(object);
        while(temp!=root){
            splay(temp);
            temp=find(object);
        }
    }
    const T& min_ele(){
        if(tree_empty()){
            cout<<"Error! AVL Tree is empty!"<<endl;
            return root->element;
        }
        return find_min(root);
    }
    const T& max_ele(){
        if(tree_empty()){
            cout<<"Error! AVL Tree is empty!"<<endl;
            return root->element;
        }
        return find_max(root);
    }
    void sp_midprint(){
        mid_print(root);
    }
    void sp_midout(vector<T>& _target){
        mid_out(root,_target);
    }  
};

template <typename T>
void SP_sort(vector<T>& _data){
        sp_tree<T> tree;
        for(int i=0;i<_data.size();i++) tree.sp_insert(_data[i]);
        int size=_data.size();
        for(int i=0;i<size;i++) _data.pop_back();
        tree.sp_midout(_data);
}



#endif